COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00032 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a44.tex[154,phy] \today\hfill}

\bigskip
\line{\bf CS 254\hfill Midterm With Some Solutions}
\line{\bf Spring 1986\hfill}
\bigskip
\line{General Instructions.\hfill}

You may use all books and notes. People (preferably teaching staff) may be 
consulted only to interpret the meaning of the questions.
All answers should be shown by logically compelling argument. No
particular type of argument is compulsory; mathematical induction is a
useful tool, for example, but no one is compelled to use it.
Algorithms may be described at a high level, incorporating algorithms from
the book or lectures, by mention, as subroutines. Results that are proved
in the textbook and lectures may be used. The exam totals 100~points; check
that you have all problems. Median scores may be 50 or lower: don't panic,
the problems look hard to other people too.

\bigskip
\disleft 20pt:{\bf (1)}:
[5 points.] There are other regular expressions for the language
$(ab↑{\ast}c)↑{\ast}$, that contain only one asterisk. Find one.

\medskip
\disleft 20pt::{\bf Answer:} $\epsilon\cup a\{b\cup ca\}↑{\ast}c$ is one.
One way to prove equivalence is to construct a NFM for each, convert to DFM's,
and minimize.
For another, construct the following NFM for $(ab↑{\ast}c)↑{\ast}$:

\medskip
$$\vcenter{\halign{$\hfil#\hfil$\quad
&$\hfil#\hfil$\quad
&$\hfil#\hfil$\qquad
&$\hfil#\hfil$\qquad
&$\hfil#\hfil$\quad
&$\hfil#\hfil$\cr
0\cr
\noalign{\smallskip}
&\epsilon&&&&b\cr
&&&a\cr
\noalign{\smallskip}
&&1&&2\cr
&&&c\cr
&\epsilon\cr
\noalign{\smallskip}
3\cr}}$$

\bigskip
\disleft 20pt::
and eliminate first state 1, then state 2, simplifying regular expressions
as you go.



\bigskip
\disleft 20pt:{\bf (2)}:
[10 points.] We want to classify regular expressions according to
whether ($E$)~the languge they describe is empty~($\emptyset$),
($N$)~consists of the empty string only~($\epsilon$), ($F$)~is some
other finite language, or ($I$)~is infinite. Give an algorithm that works
directly on the regular expression (without converting it to a machine).

\medskip
\disleft 20pt::{\bf Answer:}
The simplest regular expressions, $\emptyset$, $\{\epsilon\}$, and~$\{a\}$
where $a\in\Sigma$, are immediate. If $r↓1$ and~$r↓2$ are regular expressions
already classified, we classify $r↓1\otimes r↓2$, $r↓1\cup r↓2$, and~$r↓1↑{\ast}$
as follows:

$$\vbox{\offinterlineskip
\halign{$#$\hfil$\;$&$#$&$#$&$#$&\vrule#&\strut\quad\hfil$#$\hfil%
&\quad\hfil$#$\hfil
&\quad\hfil$#$\hfil
&\quad\hfil$#$\hfil\quad
&\qquad$#$\hfil$\;$&$#$&$#$&$#$%
&\vrule#&\strut\quad\hfil$#$\hfil%
&\quad\hfil$#$\hfil
&\quad\hfil$#$\hfil
&\quad\hfil$#$\hfil\quad
&\hbox{\qquad}#&\quad\hfil$#$\hfil\quad&\vrule#&\strut\quad%
\hfil$#$\hfil\quad\cr
&&&r↓2&\omit&&&&&&&&r↓2\cr
&r↓1&&&\omit&\emptyset&\epsilon&F&I%
&&r↓1&&&\omit&\emptyset&\epsilon&F&I%
&&r↓1&\omit&r↓1↑{\ast}\cr
&&&&\multispan5\hrulefill&&&&&\multispan5\hrulefill&&\multispan3\hrulefill\cr
&&&&height2pt&\omit&\omit&\omit&\omit&\omit&\omit&\omit&&&\omit&\omit&\omit%
&\omit&\omit&&&\omit\cr
r↓1\otimes r↓2\hbox{:}&&\emptyset&&&\emptyset&\emptyset&\emptyset&\emptyset%
&r↓1\cup r↓2\hbox{:}&&\emptyset&&&\emptyset&\epsilon&F&I&&\emptyset&&\epsilon\cr
&&\epsilon&&&\emptyset&\epsilon&F&I%
&&&\epsilon&&&\epsilon&\epsilon&F&I&&\epsilon&&\epsilon\cr
&&F&&&\emptyset&F&F&I%
&&&F&&&F&F&F&I&&F&&I\cr
&&I&&&\emptyset&I&I&I%
&&&I&&&I&I&I&I&&I&&I\cr}}$$

\vfill\eject

%\bigskip
\disleft 20pt:{\bf (3)}:
[10 points.] Machine $M$ is a 5-state DFM that accepts $a↑{21}b↑{37}$.

\display 40pt:{\bf (A)}:
Can we infer whether $M$ accepts or rejects $a↑{261}b↑{97}$?

\display 40pt:{\bf (B)}:
Can we infer whether $M$ accepts or rejects $a↑{81}b↑{55}$?

\medskip
\disleft 20pt::{\bf Answer:}
\display 40pt:{\bf (A)}:
Yes, the pumping lemma implies a pumpable string of length 1, 2, 3, 4,
or~5 among the $a$'s and the~$b$'s; all divide
$261-21=240$ and $97-37=60$, so $M$~accepts.

\display 40pt:{\bf (B)}:
No, $M$ might accept the set of strings where the number of $b$'s is not
a multiple of~5 (rejecting $a↑{81}b↑{55}$) or it might accept $a↑{\ast}b↑{\ast}$
(accepting $a↑{81}b↑{55}$).


\bigskip
\disleft 20pt:{\bf (4)}:
[20 points.]
Present an algorithm that, given the transition table of a DFM that
recognizes language~$L$, and given strings~$x$ and~$y$, tests whether
$x\appL y$ (infix equivalence). The algorithm need not be efficient,
but its simplicity and correctness will endear you to those fine people
who will grade the exam.

\medskip
\disleft 20pt::{\bf Answer:}
First, minimize $M$. If $x\appL y$, then for all $u$ and~$v$,
$S\delta↓u\delta↓x\delta↓v\in F$ iff $S\delta↓u\delta↓y\delta↓v\in F$.
Since in a minimized machine, $S\delta↓u$ ranges over all states,
$x\appL y$ means for all $q\in Q$, $q\delta↓x\delta↓v\in F$ iff
$q\delta↓y\delta↓v\in F$. Two distinct states $q'$ and~$q''$ are always
distinguishable by some input~$v$ in a minimized machine, so
$x\appL y$ means for all $q\in Q$, $q\delta↓x=q\delta↓y$, a~proposition
readily tested by iteration over the states $q\in Q$, and over the characters
of~$x$ and~$y$.


\bigskip
\disleft 20pt:{\bf (5)}:
[15 points.]
Let $L$ be the set of strings $u\,bb\,v$ over $\{a,b\}↑{\ast}$ where the
number of $a$'s in~$u$ is a multiple of three, and the number of $a$'s
in~$v$ is a multiple of two. Find the minimized DFM recognizing~$L$.

\bigskip
\disleft 20pt:{\bf (6)}:
[10 points.]
Put the following CFG into Chomsky normal form, with no useless variables:
$$\eqalign{V&=\{S,D,E,F,G,H,I,J,K,L\}\cr
T&=\{a,b,(,),+,-,*,/,\uparrow,\downarrow\}\cr
S&\hbox{ is the root symbol}\cr
P&=\cr}$$
{}
$$\eqalign{S&→E\mid GF\cr
E&→D\mid -D\mid EK\cr
D&→F\mid D*F\mid D/F\cr
F&→a\mid b\mid (E)\mid GI\cr
G&→G\uparrow H\mid H\cr
H&→H\downarrow G\mid GD\cr
I&→*J\cr
J&→E\cr
K&→+DL\mid -DL\mid\epsilon\cr
L&→\epsilon\mid E\cr}$$

\bigskip
\disleft 20pt:{\bf (7)}:
[10 points.]
Give a direct method (not converting to finite machines, for example)
to find a context-free grammar for a language, given a regular expression
for that language.

\medskip
\disleft 20pt::{\bf Answer:}
Trivial for base cases. E.g., for $\emptyset$, grammar has $V=\{S\}$, no
productions, any set~$T$. For $r↓1\otimes r↓2$ with grammars $G↓1$
and~$G↓2$, unite the grammars with new root symbol~$S$, $S→S↓1\otimes S↓2$.
For $r↓1\cup r↓2$, let $S→S↓1\mid S↓2$. For~$r↓1↑{\ast}$, let
$S→S↓1S\mid\epsilon$.


\bigskip
\disleft 20pt:{\bf (8)}:
[20 points total.]
Modifying the Hopcroft-Ullman definition of a PDM transition slightly,
we say that a transition is a quintuple $\langle q,x,y,z,q'\rangle$
where $q,q'\in Q$; $x\in\Sigma↑{\ast}$; $y,z\in\Gamma↑{\ast}$.
This transition allows the PDM, in one step, from control state~$q$,
to read string~$x$ from the input, pop string~$y$ off the stack, push
string~$z$ on the stack, and enter control state~$q'$. Such a transition
changes instantaneous description $\langle q,xu,yv\rangle$ to
$\langle q',u,zv\rangle$, where the first component of an $ID$ is the
control state, the second is the unread remainder of the input string,
and the third is the stack content, head on left.

\medskip
\display 40pt:{\bf (A)}:
[10 points.] Define a (finite) set of such transitions as
{\sl deterministic\/} if no $ID$ can be changed by more than one transition.
How can we test a PDM for determinism?

\medskip
\display 40pt:{\bf (B)}:
[10 points.] In such a PDM, suppose $q\in Q$, no transitions both begin and
end with~$q$, $q\notin S$, $q\notin F$. Suppose we wish to eliminate
state~$q$, by combining such pairs as, say
$$\langle q↓1,x↓1,y↓1,z↓1,q\rangle\,\langle q,x↓2,y↓2,z↓2,q↓2\rangle$$
into a single transition. What conditions are necessary in order to
combine such a pair? Give an algorithm to combine such pairs.

\medskip
\disleft 20pt::{\bf Answer:}
The two transitions can be combined only if one of $z↓1$, $y↓2$ is a
prefix of the other. Say $y↓2=z↓1w$. Then the combined effect on the 
stack is to change $y↓1wv$ to $z↓1wv=y↓2v$, into $z↓2v$, so the
new transition is
$$\langle q↓1,x↓1x↓2,y↓1w,z↓2,q↓2\rangle\,.$$
Similarly, if $z↓1=y↓2w$, the new transition is
$$\langle q↓1,x↓1x↓2,y↓1,z↓2w,q↓2\rangle\,.$$
After combining all such transitions, the transitions that contain~$q$
may be discarded.

\medskip
\disleft 20pt::{\bf Lemma:} 
If $z↓1\otimes s=y↓2\otimes t$, the string can be broken
up as $f\otimes g\otimes h$, either with
$$z↓1=f\,,\quad s=g\otimes h\,,\quad y↓2=f\otimes g\,,\quad t=h$$
or with
$$z↓1=f\otimes g\,,\quad s=h\,,\quad y↓2=f\,,\quad t=g\otimes h\,.$$
If $z↓1=\epsilon$ or $y↓2=\epsilon$ this is immediate; if not,
$z↓1=az↓1'$, $y↓2=ay'↓2$, $z↓1's=y↓2't$, and induction on length completes
the proof.


\bigskip
\parindent0pt
\copyright 1986 Robert W. Floyd
First draft (not published)
May 6, 1986.
%revised date;
%subsequently revised.

\bye